package demo;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class TreeNode {
    int val;//结点的值
    TreeNode left;//左
    TreeNode right;//右

    public TreeNode() {

    }

    public TreeNode(int val) {
        this.val = val;
    }
}


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int a;//用于遍历字符串

    //中序遍历
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //前序遍历创建二叉树
    public static TreeNode createTree(String str) {
        char ch = str.charAt(a);
        TreeNode root = null;//创建根节点
        if (ch != '#') {
            root = new TreeNode(ch);
            a++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            a++;
        }
        return root;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = new String();
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            str = in.nextLine();
        }
        TreeNode root = createTree(str);
        inOrder(root);
    }


    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();//需要返回的

        Queue<TreeNode> queue = new LinkedList<>();//使用队列来进行层序遍历
        if (root == null) {
            return ret;
        }
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                list.add(tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
            ret.add(list);
        }

        return ret;
    }
}
